package leetcode.editor.cn.q2xx

class Q213 {
    fun rob(nums: IntArray): Int {
        val n = nums.size
        if (n == 0) return 0
        if (n == 1) return nums[0]
        if (n == 2) return maxOf(nums[0], nums[1])
        return maxOf(rob(nums, 0, n - 2), rob(nums, 1, n - 1))
    }

    fun rob(nums: IntArray, from: Int, to: Int): Int {
        val n = to - from + 1
        if (n <= 0) return 0
        if (n == 1) return nums[from]
        if (n == 2) return maxOf(nums[from], nums[from + 1])
        val dp = IntArray(n + 1)
        dp[0] = 0
        dp[1] = nums[from]
        dp[2] = maxOf(nums[from], nums[from + 1])
        for (i in 3..n) {
            dp[i] = maxOf(dp[i - 2] + nums[from + i - 1], dp[i - 1])
        }
        return dp[n]
    }
}